package mergesort;

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int [] a = {-5,6,3,8,9,-21,23,1,2};
        MergeSort mergeSort = new MergeSort();
        mergeSort.divide(a,0,a.length-1);
    }

    public void divide(int [] array,int left,int right){
        if(left < right){
            int mid = (left + right) / 2;
            divide(array,left, mid);
            divide(array,mid+1, right);
            merge(array,left,mid,right);
        }

    }

    public void  merge(int [] array,int left,int mid,int right){

        int[] temp = new int[right - left + 1];
        int i=left;int j=mid+1;int k=0;

        while (i<=mid&&j<=right){

            if (array[i] < array[j]){
                temp[k++] = array[i++];
            }else{
                temp[k++] = array[j++];
            }

        }

        while (i<=mid){
            temp[k++] = array[i++];
        }
        while (j<=right){
            temp[k++] = array[j++];
        }

        //放回原数组
        for (int x = 0; x < temp.length; x++) {
            array[left+x] = temp[x];
        }

        System.out.println("Sorting: " + Arrays.toString(array));

    }


}
